#include <iostream>
/*
 假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m （1 ≤ m ≤ n） 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个非负整数数组代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数。如果不能使每台洗衣机中衣物的数量相等，则返回 -1。

 

示例 1：

输入: [1,0,5]

输出: 3

解释: 
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2   
示例 2：

输入: [0,3,0]

输出: 2

解释: 
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1     
示例 3:

输入: [0,2,0]

输出: -1

解释: 
不可能让所有三个洗衣机同时剩下相同数量的衣物。

 * */
/*
 解析:
  假如有四个洗衣机，装的衣服数为[0, 0, 11, 5]，
  最终的状态会变为[4, 4, 4, 4]，那么我们将二者做差，
  得到*[-4, -4, 7, 1]，这里负数表示当前洗衣机还需要的衣服数，
  正数表示当前洗衣机多余的衣服数。我们要做的是*要将这个差值数组
  每一项都变为0，对于第一个洗衣机来说，需要四件衣服可以从第二个
  洗衣机获得，那么就可以 把-4移给二号洗衣机，那么差值数组变为
  [0, -8, 7, 1]，此时二号洗衣机需要八件衣服，那么至少需要移动8次。
  然后二号洗衣机把这八件衣服从三号洗衣机处获得，
  那么差值数组变为[0, 0, -1, 1]，此时三号洗衣机还缺1件，
  就从四号洗衣机处获得，
  此时差值数组成功变为了[0, 0, 0, 0]，成功
  。那么移动的最大次数就是差值 数组中出现的绝对值最大的数字，8次。（下面的代码来自评论区）
 * */
#include <vector>
#include <algorithm>

using namespace std ;
class Solution{
public :
    int findMinMoves(vector<int>&machines) {
        //求和
        int sum = accumulate(machines.begin(), machines.end(), 0) ;
        int len = machines.size() ;
        int res = 0, cnt = 0, avg = sum/len ;
        for(auto m:machines) {
            cnt += m-avg ;//如果cnt与m-avg同号，则会积累，否则就会进行抵消
            //m-avg代表的是移平m需要的步骤数，max(abs(cnt), m-avg)，从之前
            //移平m需要的步骤数
            res = max(res, max(abs(cnt), m-avg)) ; 
        }
        return res ;
    }
};

int main()
{
    std::cout << "Hello world" << std::endl;
    return 0;
}

